package HashMap;

import java.util.HashMap;

/**
 *  题目 ：外星语言是否排序
 *  题目详述 ：
 *  某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
 * 给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。
 *
 */
public class OfferP34 {
    /**
     *  核心思想 ：
     *  使用哈希表，来存储字母表的顺序（key ：字母 ；value ：其在字母表（字母表字符串）中的顺序）
     *  方法一 ：使用hashmap，对其进行存储（适用于所有字符）
     *  方法二 ：使用数组（局限性在于，必须明确知道字母表中字母数目）
     */
    HashMap<Character,Integer> map;
    public boolean isAlienSorted(String[] words, String order) {
        int i = 0;
        map = new HashMap<>();
        for (char c : order.toCharArray()) {
            // 即，将代表字母表顺序的字符串读入hashmap中（key ：代表char值；value，代表其在字母表中顺序）
//            System.out.println(c + "===》" + i);
            map.put(c,i++);
        }

        for (int j = 0; j < words.length - 1; j++){
            if(!isNotSorted(words[j],words[j + 1])){
                return false;
            }
        }
        return true;
    }

    private boolean isNotSorted(String word1, String word2) {
        // 使用字符数组来存储word1和word2中的每个字符
        char[] word1ToChars = word1.toCharArray();
        char[] word2ToChars = word2.toCharArray();
        int i = 0;
        while(i < word1.length() && i < word2.length()){  // 对于word1和word2中，每个字符顺序地进行比较
            // 情况一 ：若是word1中字符 < word2中的字符，即返回 true
            if (map.get(word1ToChars[i]) < map.get(word2ToChars[i])){
                return true;
            }
            // 情况二 ：若是word1中字符 > word2中的字符，即返回 true
            if(map.get(word1ToChars[i]) > map.get(word2ToChars[i])){
                return false;
            }
            // 情况三 ：若是word1中字符 == word2中的字符，即使得i++（后续字符继续进行比较）
            i++;
        }
        // 极端情况 ：即，word1和word2的前面字符一致，但是word2的长度小于word1的长度，即需要返回 false
        return i == word1.length();
    }
}
